Servers, switches, routers, and other computing devices which process many tasks require a scheduler to set the order in which tasks will be executed. As tasks arise, a task manager places the tasks within a work queue. The scheduler retrieves tasks from the work queue one at a time, and places them into a job queue. The computing device executes tasks within the job queue using resources. Since resources are limited, only a limited number of tasks can be in the job queue at any given time. If each task has an associated priority, then the scheduler should place the tasks into the job queue such that higher priority tasks are executed before lower priority tasks.
One form of scheduling which allows priorities to be set is multi-level exhaustive scheduling. Each task has one of a set of ordered priorities, and is binned within the work queue according to its priority. More than one task can have the same priority, and there may be more than one task within the work queue at each of the set of priorities. This is the “multi-level” aspect of the scheduling. The scheduler first selects a task within the work queue for which no other task has a higher priority, and places it in the job queue. The scheduler then repeats this for other tasks. In this way, all the tasks having the highest priority are scheduled before any task of the second highest priority are scheduled, and so on for tasks of each priority within the set of priorities. This is the “exhaustive” aspect of the scheduling. If a new task having the highest priority arrives in the work queue while the scheduler is scheduling tasks having the second highest priority, the scheduler stops scheduling tasks having the second highest priority and schedules instead the new task.
Schedulers typically place tasks within the job queue based on their priority within the work queue. Tasks are therefore selected one at a time from the job queue for execution, higher priority tasks being executed before lower priority tasks. This is true even for tasks which could otherwise be executed simultaneously. Each task within the job queue requires resources for execution, so one package is sent to one line card for transmission, and then an identical package (other than destination) is sent to a second line card for transmission. The scheduler treats each of the two tasks separately, scheduling each one within the job queue independently. This delays execution of tasks of lower priority, since computing resources must fully process the two separate tasks independently before processing of lower priority tasks can occur.
One way in which schedulers improve efficiency of the job queue is to not schedule tasks for which there are insufficient resources to execute the task. When the scheduler selects a task from the work queue, the scheduler determines whether there are sufficient resources (as examples, available line cards, bandwidth, or slot numbers) to execute the task. If there are insufficient resources to execute the task, the scheduler rejects the task. If the resource insufficiency is only temporary, then the task may be rejected unnecessarily. A scheduler that took advantage of multi-tasking and that did not reject high priority tasks unnecessarily would improve efficiency of task execution.